package com.zhangx.datastructure.graph;

import java.util.Arrays;
import java.util.Stack;

/**
 * @ClassName CriticalPath
 * @Description 关键路径
 * @Author zhangx
 * @Date 2021/1/20 8:28
 **/
public class CriticalPath {

    int MAXVEX = 10;
    VertexNode[] adjList = new VertexNode[MAXVEX];
    int numVertexes;//顶点数
//    int numEdges;//边数
//    stack2指针
    int top2 = 0;
    //事件最早发生时间数组
    int[] etv = new int[MAXVEX];
//  最迟发生时间
    int[] ltv = new int[MAXVEX];
//    存储拓扑序列的栈，为了求关键路径
    Stack<Integer> stack2 = new Stack<>();
    /**
     * 边表节点,顶点的出度
     */
    class EdgeNode{
        int weight;
        int adjvex;//在顶点数组中的下标
        EdgeNode next;

        public EdgeNode(int adjvex, EdgeNode next){
            this.adjvex = adjvex;
            this.next = next;
        }
        public EdgeNode(int adjvex){
            this.adjvex = adjvex;
        }
        public EdgeNode(int adjvex,int weight){
            this.adjvex = adjvex;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "weight=" + weight +
                    ", adjvex=" + adjvex +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 顶点
     */
    class VertexNode{
        int in;//入节点
        String data;
        EdgeNode firstEdge;

        public VertexNode(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "in=" + in +
                    ", data='" + data + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "CriticalPath{" +
                "MAXVEX=" + MAXVEX +
                ", adjList=" + Arrays.toString(adjList) +
                ", numVertexes=" + numVertexes +
                '}';
    }

    /**
     * 构造链表
     * @param vData
     * @param in
     * @param first
     * @param second
     * @return
     */
    public VertexNode fillData(String vData, int in, int first,int firstWeight, int second,int secondWeight){
        VertexNode vertexNode = new VertexNode(vData);
        vertexNode.in = in;
        if (first > 0){
            EdgeNode a = new EdgeNode(first,firstWeight);
            if (second > 0){
                EdgeNode b = new EdgeNode(second,secondWeight);
                a.next = b;
            }
            vertexNode.firstEdge = a;
        }
        return vertexNode;
    }

    void init(){
//        初始化AOE网
        numVertexes = 10;
        MAXVEX = 10;
        adjList = new VertexNode[MAXVEX];
        adjList[0] = fillData("v0",0,2,4,1,3);
        adjList[1] = fillData("v1",1,4,6,3,5);
        adjList[2] = fillData("v2",1,5,7,3,8);
        adjList[3] = fillData("v3",2,4,3,0,0);
        adjList[4] = fillData("v4",2,7,4,6,9);
        adjList[5] = fillData("v5",1,7,6,0,0);
        adjList[6] = fillData("v6",1,9,2,0,0);
        adjList[7] = fillData("v7",2,8,5,0,0);
        adjList[8] = fillData("v8",1,9,3,0,0);
        adjList[9] = fillData("v9",2,0,0,0,0);
    }

    String topologicSort(){
        String result = "OK";

        int top = 0;
        int count = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numVertexes; i++) {

            if (adjList[i].in == 0){
                ++top;
                stack.push(i);
            }
        }
//        -------------------
        top2 = 0;
        etv = new int[MAXVEX];
//        -------------------
//        不断的在栈中遍历
        while (top!=0){
            top--;
            int gettop = stack.pop();
            System.out.println(adjList[gettop].data);
            count++;
//        -------------------
            ++top2;
            stack2.push(gettop);
//        -------------------
//            循环入度=0的链表
            for (EdgeNode e = adjList[gettop].firstEdge; e!=null; e =e.next){
                int k = e.adjvex;
//                将他们入度-1，就是去除一条连线
                if ((--adjList[k].in)==0){
                    ++top;
//                    如果这个节点的入度=0，加到栈中
                    stack.push(k);//0则入栈
                }
//        -------------------
                if ((etv[gettop]+e.weight)>etv[k]){
                    etv[k] = etv[gettop] + e.weight;
                }
//        -------------------
            }

        }
        if (count < numVertexes){
//            所有顶点都输入，就不是环形的，没有回路
            result = "OK";
        }
        return result;
    }

    void path(){
        EdgeNode e;
        int ete,lte = 0;//活动最早发生时间和最迟发生时间变量
        topologicSort();//求etv和stack2
        ltv = new int[MAXVEX];
        for (int i = 0; i < numVertexes; i++) {
            ltv[i] = etv[numVertexes-1];
        }
        while (top2!=0){
            int gettop = stack2.pop();
            top2--;//后进先出
            for (e = adjList[gettop].firstEdge;e!=null;e=e.next){
//                求各顶点最迟发生时间ltv
                int k = e.adjvex;
                if ((ltv[k]-e.weight)<ltv[gettop]){
                    ltv[gettop] = ltv[k] - e.weight;
                }
            }
        }
        for (int j = 0; j < numVertexes; j++) {
            for(e = adjList[j].firstEdge;e!=null;e=e.next){
                int k = e.adjvex;
                ete = etv[j];//活动最早发生时间
                lte = ltv[k] - e.weight;//活动最迟发生时间
                if (ete == lte){//中间没有空闲就是关键点
                    System.out.printf("<%s,%s> length: %d\n",adjList[j].data,adjList[k].data,e.weight);
                }

            }
        }
    }

    public static void main(String[] args) {
        CriticalPath criticalPath = new CriticalPath();
        criticalPath.init();
        System.out.println(criticalPath);
        criticalPath.path();
    }

}
